/*
 * Verfahren zur Berechnung einer konvexen Hülle von einer Menge von Punkten. (Jarvis March Algorithmus)
 */

package de.hsb.ai.agent.misterx.brain.geoanalyser;

import de.hsb.ai.agent.misterx.brain.geoanalyser.CHPoint;

public class ConvexHull {
	private CHPoint[] p;
    private int n;
    private int h;

    public int computeHull(CHPoint[] p) {
        this.p = p;
        n = p.length;
        h = 0;
        this.jarvisMarch();
        return h;
    }

    private void jarvisMarch() {
        int i=indexOfLowestPoint();
        do {
            exchange(h, i);
            i=indexOfRightmostPointFrom(p[h]);
            h++;
        }
        while (i>0);
    }

    private int indexOfLowestPoint() {
        int i, min=0;
        for (i=1; i<n; i++)
            if (p[i].y<p[min].y || p[i].y==p[min].y && p[i].x<p[min].x)
                min=i;
        return min;
    }

    private int indexOfRightmostPointFrom(CHPoint q) {
        int i=0, j;
        for (j=1; j<n; j++)
            if (p[j].relTo(q).isLess(p[i].relTo(q)))
                i=j;
        return i;
    }

    private void exchange(int i, int j) {
        CHPoint t=p[i];
        p[i]=p[j];
        p[j]=t;
    }

	
	
	
	
}
